/*
 * redBlackTree.h
 * This file is part of Jamming
 *
 * Copyright (C) 2012 - Yi
 *
 * Jamming is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Jamming is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Jamming. If not, see <http://www.gnu.org/licenses/>.
 */


#ifndef __REDBLACKTREE_H__
#define __REDBLACKTREE_H__
#include <cstring>
namespace Tree
{
    template < typename _TypeData>
    class RBtree {
        struct Node {
            _TypeData data;
            bool black;
            Node* left;
            Node* right;
        };

        Node* root;
        inline rightRotate(Node* ptrBaseNode) {
            Node* newBase=ptrBaseNode->left;
            ptrBaseNode->left=newBase->left;
            newBase->left=ptrBaseNode->right;
            ptrBaseNode->right=ptrBaseNode;
            _TypeData tmp;
            bool tmpcolor;
            tmp=newBase->left->data;newBase->left->data=newBase->right->data;newBase->right->data=tmp;
            tmp=ptrBaseNode->data;newBase->data=ptrBaseNode->data;ptrBaseNode->data=tmp;
            tmpcolor=newBase->left->black;newBase->left->black=newBase->right->black;newBase->right->black=tmpcolor;
            tmpcolor=ptrBaseNode->black;newBase->black=ptrBaseNode->black;ptrBaseNode->black=tmpcolor;
        };
        inline leftRotate(Node* ptrBaseNode) {
            Node* newBase=ptrBaseNode->right;
            ptrBaseNode->right=newBase->right;
            newBase->right=ptrBaseNode->left;
            ptrBaseNode->left=ptrBaseNode;
            _TypeData tmp;
            bool tmpcolor;
            tmp=newBase->left->data;newBase->left->data=newBase->right->data;newBase->right->data=tmp;
            tmp=ptrBaseNode->data;newBase->data=ptrBaseNode->data;ptrBaseNode->data=tmp;
            tmpcolor=newBase->left->black;newBase->left->black=newBase->right->black;newBase->right->black=tmpcolor;
            tmpcolor=ptrBaseNode->black;newBase->black=ptrBaseNode->black;ptrBaseNode->black=tmpcolor;
        };
        public:
        insert(_TypeData data) {
            Node* ptrNode=root;
            Node* ptrParent,ptrGrandparent,ptrUncle;
            Node* ptrUpperNode,ptrLowerNode;
            bool isLeft;
            //find the place to insert
            while(!ptrNode) {
                if(data <ptrNode->data) {
                    ptrParent=ptrUpperNode=ptrNode;ptrNode=ptrNode->left;isLeft=true;
                }
                if(data >ptrNode->data) {
                    ptrParent=ptrLowerNode=ptrNode;ptrNode=ptrNode->right;isLeft=false;
                }
                if(data == ptrNode->data) { return}  // If multiple map,Same key-> collision handle
            }
            // add new node
            ptrNode= new Node;
            ptrNode->data=data;
            ptrNode->black=false;
            //if root is NULL
            if(!root) {root=ptrNode;root->black=true;return;}
            ptrGrandparent=ptrParent==ptrLowerNode?ptrUpperNode:ptrLowerNode;
            if(isLeft) {ptrParent->left=ptrNode;}
            else ptrParent->right=ptrNode;
            // case 0: if no grandparent
            if(!ptrGrandparent) return;
            ptrUncle=ptrParent==ptrGrandparent->left?ptrGrandparent->right:ptrGrandparent->left;
            // case 1: uncle is red 
            if(ptrUncle&&!ptrUncle->black) {ptrGrandparent->black=false;ptrUncle->black=ptrParent->black=true;} 
            else if(isLeft) {
            // case 2: uncle is black. Node is left child. Right-rotate
                rightRotate(ptrGrandparent);
            } else {
            // case 3: uncle is black.is right child. Left rotate
                leftRotate(ptrGrandparent);
            }
        };
        remove(_TypeData data) {
            Node* ptrNode=root;
            Node* ptrParent,ptrGrandparent,ptrUncle;
            Node* ptrUpperNode,ptrLowerNode,ptrToReomve;
            bool isLeft;
            //find the place to insert
            while(!ptrNode) {
                if(data <ptrNode->data) {
                    ptrParent=ptrUpperNode=ptrNode;ptrNode=ptrNode->left;isLeft=true;
                }
                if(data >ptrNode->data) {
                    ptrParent=ptrLowerNode=ptrNode;ptrNode=ptrNode->right;isLeft=false;
                }
                if(data == ptrNode->data) ptrToReomve=ptrNode;  
            }
            if(!ptrToReomve) raise keyNotExist(); //not found, nothing to be deleted.
            //If multiple map, reduce count but do not delete the node.
            //no child
            if(!ptrToReomve->left&&!ptrToReomve->right) { ptrParent=NULL;delete ptrToReomve;return;}
            //one child
            if(!ptrToReomve->left) { ptrToReomve->data=ptrToReomve->right;delete ptrToReomve->right; return;}
            if(!ptrToReomve->right) { ptrToReomve->data=ptrToReomve->left;delete ptrToReomve->left; return;}
            //two child
            ptrToReomve->data=ptrUpperNode->data;
        };
        Node* find(_TypeData data){
            Node* ptrNode=root;
            while(!ptrNode) {
                if(data <ptrNode->data) ptrNode=ptrNode->left;
                if(data >ptrNode->data) ptrNode=ptrNode->right;
                if(data == ptrNode->data) return ptrNode;
            }
            return NULL;
        };
        Node* lower_bound(_TypeData data) {
            Node* ptrNode=root;
            Node* ptrLowerNode,ptrUpperNode;
            while(!ptrNode) {
                if(data <ptrNode->data) {ptrUpperNode=ptrNode;ptrNode=ptrNode->left;}
                if(data >ptrNode->data) {ptrLowerNode=ptrNode;ptrNode=ptrNode->right;}
            }
            return ptrLowerNode;
        };
        Node* upper_bound(_TypeData data){
            Node* ptrNode=root;
            Node* ptrLowerNode,ptrUpperNode;
            while(!ptrNode) {
                if(data <ptrNode->data) {ptrUpperNode=ptrNode;ptrNode=ptrNode->left;}
                if(data >ptrNode->data) {ptrLowerNode=ptrNode;ptrNode=ptrNode->right;}
            }
            return ptrUpperNode;
        };
        merge_in(Node* treeRoot);
        //TODO set operation: union,difference,common. This is not quite efficient in RB-Tree.
        // consider Treap,splay tree. 
        _TypeData min(){
            Node* node=root;
            if(!root) raise notInitialized(); 
            while(!node->left) node=node->left;
            return node->data;
        };
        _TypeData max(){
            Node* node=root;
            if(!root) raise notInitialized(); 
            while(!node->right) node=node->right;
            return node->data;
        };
    };
};


#endif /* __REDBLACKTREE_H__ */

